﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
class Sol54
{
    IList<int> res2 = new List<int>();

    public IList<int> SpiralOrder2(int[][] matrix)
    {
        IList<int> res = new List<int>();

        int m = matrix.Length;
        int n = matrix[0].Length;
        if (n == 0 || m == 0)
        {
            return res;
        }


        //使用visted记录走过的路径,也可以使用原来的矩阵，但是会破坏
        bool[][] visted = new bool[m][];
        for (int i = 0; i < m; i++)
        {
            visted[i] = new bool[n];
        }

        int colIndex = 0;
        int rowIndex = 0;

        //int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int[][] directions = new int[4][];
        directions[0] = [0, 1];
        directions[1] = [1, 0];
        directions[2] = [0, -1];
        directions[3] = [-1, 0];

        int directionsIndex = 0;

        //int[] nums = new int { 1, 3 };

        while (res.Count < m * n)
        {

            res.Add(matrix[rowIndex][colIndex]);

            visted[rowIndex][colIndex] = true;
            //出界或者访问过，就转方向
            int nextrowIndex = rowIndex + directions[directionsIndex][0];
            int nextcolIndex = colIndex + directions[directionsIndex][1];
            if (nextrowIndex == m || nextcolIndex == n || nextrowIndex < 0 || nextcolIndex < 0 || visted[nextrowIndex][nextcolIndex])//越界,两种情况，0或者超出
            {
                directionsIndex = (directionsIndex + 1) % 4;
            }


            rowIndex += directions[directionsIndex][0];
            colIndex += directions[directionsIndex][1];




        }






        return res;

    }
    public IList<int> SpiralOrder(int[][] matrix)
    {
        IList<int> res = new List<int>();

        int m = matrix.Length;
        int n = matrix[0].Length;
        if (n == 0 || m == 0)
        {
            return res;
        }

        int left = 0;
        int right = n - 1;
        int top = 0;
        int bottom = m - 1;

      
            //终止条件


            while (left <= right && top <= bottom)
        {
            //left==right,的时候，只求//第一排（包括右上角）
            for (int col = left; col <= right; col++)//第一排（包括右上角）
            {


                res.Add(matrix[top][col]);
                Console.WriteLine("matrix[top][col]"+matrix[top][col]);

            }
            //left==right,的时候，只求//第一排（包括右上角），但是可能有两排，
            for (int row = top + 1; row <= bottom; row++)//最后一列（ top+1排除右上角），但是包括右下角
            {

                res.Add(matrix[row][right]);
                Console.WriteLine("matrix[row][right]" + matrix[row][right]);

            }

            if (left < right && top < bottom)
            {
               
                for (int newcol = right-1; newcol > left; newcol--)//最后一行，排除右下角和左下角
                {


                    res.Add(matrix[bottom][newcol]);
                    Console.WriteLine("matrix[bottom][newcol]" + matrix[bottom][newcol]);



                }
                for (int newrow = bottom; newrow > top; newrow--)//第一列，排除左上角
                {
                    res.Add(matrix[newrow][left]);
                    Console.WriteLine("matrix[newrow][left]" + matrix[newrow][left]);
                }
            }
            



            left++;
            right--;
            top++;
            bottom--;


        }




    


        return res;

    }
private void DFS(int[][] matrix, int m, int n, int i, int j)//很烂的方法，手工判断，想办法自动判断
                                                            //这个方法有点用，但是m-2不行，使用left，right，top，bottom一起确定
{

    if (m <= 0 || n <= 0) return;

    Console.WriteLine("i" + i + "n" + n);
    Console.WriteLine("j" + j + "m" + m);
    while (i < n)
    {

        res2.Add(matrix[j][i]);
        Console.WriteLine(matrix[j][i]);
        i++;
    }
    i--;
    j++;
    while (j < m)
    {

        res2.Add(matrix[j][i]);
        Console.WriteLine(matrix[j][i]);
        j++;
    }
    j--;
    i--;
    while (i >= 0)
    {

        res2.Add(matrix[j][i]);
        Console.WriteLine(matrix[j][i]);
        i--;
    }
    i++;
    j--;
    while (j > 0)
    {

        res2.Add(matrix[j][i]);
        Console.WriteLine(matrix[j][i]);
        j--;
    }
    DFS(matrix, m - 2, n - 2, i + 1, j + 1);
}
}

class Program54
{

    static void Main54(string[] args)
    {
        int m = 2;
        int n = 1;

        int[][] martx = new int[m][];
        for (int i = 0; i < martx.Length; i++)
        {
            martx[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                martx[i][j] = i * n + j + 1;
            }
        }

        int[][] martx2 = [[1, 3, 4], [3, 4, 5]];
        //for (int i = 0; i <m; i++)
        //{
        //    for (int j = 0; j < n; j++)
        //    {
        //        Console.Write(martx[i][j]+"        ");
        //    }
        //    Console.WriteLine();
        //}

        Sol54 sol = new Sol54();
        IList<int> res = sol.SpiralOrder(martx);
        for (int i = 0; i < res.Count; i++)
        {
            Console.WriteLine(res[i]);
        }
    }
}



